{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### 60. Permutation Sequence\n",
    "\n",
    "The set [1,2,3,...,n] contains a total of n! unique permutations.\n",
    "\n",
    "By listing and labeling all of the permutations in order, we get the following sequence for n = 3:\n",
    "\n",
    "    1. \"123\"\n",
    "    2. \"132\"\n",
    "    3. \"213\"\n",
    "    4. \"231\"\n",
    "    5. \"312\"\n",
    "    6. \"321\"\n",
    "Given n and k, return the kth permutation sequence.\n",
    "\n",
    "**Note**:\n",
    "- Given n will be between 1 and 9 inclusive.\n",
    "- Given k will be between 1 and n! inclusive.\n",
    "\n",
    "    Example 1:\n",
    "        Input: n = 3, k = 3\n",
    "        Output: \"213\"\n",
    "    Example 2:\n",
    "        Input: n = 4, k = 9\n",
    "        Output: \"2314\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [],
   "source": [
    "from math import factorial\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def combination(self, items, n):\n",
    "        def skipIthItem(items, i):\n",
    "            return items[: i] + items[i + 1:]\n",
    "        return self.__combinator(skipIthItem, items, n)\n",
    "\n",
    "    def __combinator(self, handle, items, n):\n",
    "        if n == 0:\n",
    "            yield []\n",
    "        for i, item in enumerate(items):\n",
    "            this_one = [item]\n",
    "            for next_one in self.__combinator(handle, handle(items, i), n - 1):\n",
    "                yield this_one + next_one\n",
    "\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        template = [i for i in range(1, n + 1)]\n",
    "        ans = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            div, k = divmod(k, factorial(i))\n",
    "            if k == 0:\n",
    "                ans.append(template[div - 1])\n",
    "                template.pop(div - 1)\n",
    "                template.reverse()\n",
    "                ans.extend(template)\n",
    "                break\n",
    "            elif k == 1:\n",
    "                ans.append(template[div])\n",
    "                template.pop(div)\n",
    "                ans.extend(template)\n",
    "                break\n",
    "            elif k == 2:\n",
    "                ans.append(template[div])\n",
    "                template.pop(div)\n",
    "                template[-2], template[-1] = template[-1], template[-2]\n",
    "                ans.extend(template)\n",
    "                break\n",
    "            else:\n",
    "                ans.append(template[div])\n",
    "                template.pop(div)\n",
    "        return ''.join(map(str, ans))\n",
    "\n",
    "\n",
    "S = Solution()"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "132\n"
     ]
    }
   ],
   "source": [
    "n = 3\n",
    "k = 2\n",
    "print(S.getPermutation(n, k))\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2314\n"
     ]
    }
   ],
   "source": [
    "n = 4\n",
    "k = 9\n",
    "print(S.getPermutation(n, k))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "498723156\n"
     ]
    }
   ],
   "source": [
    "n = 9\n",
    "k = 161191\n",
    "print(S.getPermutation(n, k))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n"
     ]
    }
   ],
   "source": [
    "n = 2\n",
    "k = 1\n",
    "print(S.getPermutation(n, k))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "n = 1\n",
    "k = 1\n",
    "print(S.getPermutation(n, k))\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}